1. Technical Field
The present invention relates generally to computer systems, and more specifically to a debugger suitable for use with rule-based expert systems.
2. Description of the Related Art
Expert systems are computer programs which attempt to mimic expert problem-solving behavior. They are typically used to draw conclusions from a set of observations or to propose and confirm hypotheses in order to achieve a desired goal. These systems employ rules as their basic components and manipulate the rules using a control procedure, such as forward-chaining or backward-chaining, in order to solve a particular problem.
Rules are statements of the form "IF condition, THEN action, ELSE action." The condition states one or more facts that must be true for the rule to be applied. The action parts state which actions should be taken when the rule is true or false. Actions for the true and false cases are found in the THEN and ELSE parts, respectively. The condition and actions frequently refer to variables which temporarily store information about the state of the problem solution. Thus, the action in one rule might assign a value to a variable which is used in the condition or action of another rule.
While each rule is considered an independent unit and is entered and processed in a declarative manner, the sharing of variables between rules allows them to interact. In forward-chaining systems, the effects of rule firings are propagated by repeatedly checking to see if rule conditions are true. A set of initial variable values is matched against the rule conditions. As rule conditions become true, the appropriate rule actions are executed and the resulting variable values are matched. This match-execution cycle is repeated until certain stopping conditions are met or until no rule actions can be executed.
In backward-chaining systems, the rules are used to establish values for goal variables. A set of variables are initially established as goals. Rules whose actions assign values to these variables are viewed as sources. The conditions of these rules may contain variables. If these variables have values, the rules may be evaluated to obtain values for the goals. If these variables do not have values, they are established as subgoals and additional rules are used as sources. This procedure continues until conditions can be evaluated and the effects of the rule actions ripple back through the chain of source rules, eventually assigning values to the original goal variables.
Many inference engines allow non-rule sources to be used. Frequently, function calls, database accesses, or user queries may be used to acquire a value for a variable. However, these sources don't contribute to the propagation of values in forward-chaining or to the pursuit of goals and subgoals in backward-chaining. Thus, the use of such sources to supply values for variables does not affect the interactions of rules in an expert system.
The fact that the rules may be entered in a declarative fashion and then executed in a manner which depends on the nature of the problem and data in a knowledge base means that the expert system programmer does not normally need to specify procedural interactions among rules. However, when the system does not display the desired behavior, it is often very difficult to determine exactly where the execution went awry. In typical expert systems, explanation facilities are provided in order to let the user view a trace of the steps which the expert system used to arrive at its conclusion. However, these explanations do not suffice to easily identify the problem in many cases, and are generally available only when the system needs the user to supply values or after the program has completed execution. Intermediate results of execution activities are frequently unavailable.
Typical prior art expert system debuggers include Knowledge Tool, a product available from IBM, and TEIRESIAS. Knowledge Tool uses forward-chaining and allows a user to single step through the inferencing process. The debugger halts at the end of the match-execution cycle and presents limited state information. Some static information is available before and after system execution.
TEIRESIAS, described in detail in Part 2 of KNOWLEDGE-BASED SYSTEMS IN ARTIFICIAL INTELLIGENCE, R. Davis and D. Lenat, McGraw-Hill, 1982, applies to backward-chaining systems. Limited state information can be obtained when execution halts while awaiting input of a variable value from a user. If a variable is changed, execution is restarted from the beginning.
Similar problems exist in conventional, procedural programming environments. Since the programs are written as explicit procedures, the flow of execution is generally obvious. However, the effects of variable values and intermediate results are not visible during execution. Conventional debuggers address this problem by allowing the user to specify breakpoints, which are points at which execution is halted and the user is allowed to investigate variable values and execution information.
Neither of the expert system debuggers mentioned above allow breakpoints to be defined based upon various conditions, such as variable values and rule firings, which occur during execution of an expert system. Neither is suitable for use with both forward-chaining and backward-chaining inference engines. Both utilize only a few simple debugging techniques typically found in conventional debuggers.
Since the flow of execution in a declarative, rule-based expert system is not generally known in advance, and may not even be deterministic, the approaches used in conventional debuggers are not adequate for use with expert system programs. It would be desirable for a debugger suitable for use with rule-based expert systems to provide breakpoint and user information facilities which clarify the operation of such expert systems and simplify the user's task of correcting programming errors. It would be further desirable to provide a method for resetting, or rolling back, execution of an expert system to an earlier state and allow execution of the expert system to be restarted from such earlier state.